/**
 * Created with IntelliJ IDEA
 * Details about unstoppable_t:
 * User: Administrator
 * Date: 2021-03-24
 * Time: 11:54
 * 根据前序遍历结果和中序遍历结果建立二叉树
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val){
        this.val = val;
    }

 }
public class BuildBinarytree {
    public int i;

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        //1.判断特殊情况 数组为空或者数组长度为0
        if(pre == null || in == null || pre.length == 0 || in.length == 0){
            return null;
        }
        return buildTreeChild(pre,in,0,in.length-1);

    }


    public TreeNode buildTreeChild(int[] preorder, int[] inorder, int start, int end){
        //判断区间
        if(start > end){
            return null;
        }
        //从前序遍历中创建根结点
        TreeNode newNode = new TreeNode(preorder[i]);
        //在中序遍历中找到该结点位置
        int index = findVal(inorder,preorder[i],start,end);
        //让i向后走，而后创建根结点的左树，然后创建右树
        i++;
        newNode.left = buildTreeChild(preorder,inorder,start,index-1);
        newNode.right = buildTreeChild(preorder,inorder,index+1,end);
        return newNode;
    }


    public int findVal(int[] inorder, int target, int first, int last){
        for(int j = first; j <= last; j++){
            if(inorder[j] == target){
                return j;
            }
        }
        return -1;
    }
}

